package com.example.leetcode.tree;

/**
 *
 * 二叉搜索树的后序遍历序列
 *
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
 * <p>
 * 提示：
 * 1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。
 * 2.该题我们约定空树不是二叉搜索树
 * 3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历
 * 4.参考下面的二叉搜索树，示例 1
 * <p>
 * <p>
 * 132  true
 * <p>
 * 递归法。  思路: 以最后一个节点为根节点; 寻找到中间的分界点;切割后分别递归两个节点;当单个节点不可分割的时候，结束递归。
 */
public class Tree1 {

    public static void main(String[] args) {

    }

    public static boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }

        // 0 到 sequence.length -1 是一棵树
        return order(sequence, 0, sequence.length -1);
    }

    public static boolean order(int[] sequence, int l, int r) {
        // 剩余一个节点的时候
        if (l >= r) {
            return true;
        }

        //多处应用，抽取为全局变量
        int j;
        //根节点
        int root = sequence[r];

        // 找到第一个小于root的结点的索引
        for (j = r - 1; l <= j; j--) {
            if (sequence[j] < root) {
                break;
            }
        }

        // 判断左子树中有没有非法元素(大于root)
        for (int i = j; l <= i; i--) {
            // 左子树大于根节点
            if (sequence[i] > root) {
                return false;
            }
        }

        // 左子树 右子树
        // 左子树l到第一个小于根节点的元素j  右子树第一个不小于根节点的元素到根节点左边
        return order(sequence, l, j) && order(sequence, j + 1,  r -1);
    }
}
